#include "BTreeNode.h"
#include <math.h>		// Added for ceil function
#include <iostream>		// Added for cout


using namespace std;

// I added the following constructor in order to create
// an empty leaf buffer when a new leaf node is generated.
BTLeafNode::BTLeafNode()
{	
	memset(buffer, 0, PageFile::PAGE_SIZE);
}

// Added helper function to output entire Node contents!!!
RC BTLeafNode::printNode()
{ 
	int pid = 0;
	int sid = 0;
	int key = 0;
	int numEntry = 0;

	memcpy(&numEntry, &buffer[0], sizeof(int));
	cout << "Number of entries = " << numEntry << endl;
  
	//cout << "Keycount = " << getKeyCount() << endl;
	int i = 8;
	while (i < getKeyCount()*12)
	{
		memcpy(&pid, &buffer[i], sizeof(int));
		memcpy(&sid, &buffer[i + sizeof(int)], sizeof(int));
		memcpy(&key, &buffer[i + (2*sizeof(int))], sizeof(int));
		cout << pid << " ";
		cout << sid << " ";
		cout << key << ", ";
		i = i + 12;
	}
	cout << endl;
	cout << "NextNodePtr = " << getNextNodePtr() << endl;

	return 0; 
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{ 
	RC rc;
  
	// read the page (NOTE: page = node)
	// Before I execute the read, I need to zero out the buffer
	// so that I do not accidentally read in values from a 
	// previous read or write.
	memset(buffer, 0, PageFile::PAGE_SIZE);

	// pf is the input PageFile we are reading from.
	// The PageFile buffer is the output of the pf.read method
	// and is writing to the BTNonLeafNode private variable.
	// So, the BTNonLeafNode::read reads from the PageFile buffer
	// and writes to the BTNonLeafNode buffer.
    if ((rc = pf.read(pid, buffer)) < 0)
	{
		fprintf(stderr, "Error: Contents of leaf node could not be read. \n");
		return rc;
	}

	return 0; 
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{ 
	RC rc;

	// The PageFile buffer is the input of the pf.write method
	// which is being written to the disk page.
	// So, the BTNonLeafNode::write reads from the BTNonLeafNode buffer
	// and writes to the PageFile.
	if ((rc = pf.write(pid, buffer)) < 0)
	{
		fprintf(stderr, "Error: Contents of leaf node could not be written. \n");
		return rc;
	}

	return 0; 
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{ 
	// In the leaf node, for every record id there
	// is a key. So, to find the key count, I can
	// simply count the number of record ids.
	int count = 0;

	// The first four bytes of a page contains # entries in the page
	// and the second four bytes contains the pageid pointing to 
	// the sibling node.
	//memcpy(&count, &buffer[0], sizeof(int));
	memcpy(&count, &buffer, sizeof(int));
	//cout << "count = " << count << endl;
	return count;

	//return 0; 
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{ 
	// This insert function is similar to RecordFile's
	// append function. At first, I thought I needed to
	// just search for an empty space in the node and 
	// then insert the rid and key to this
	// spot. If there is no empty spot, then the node is
	// full. However, I then realized that I need to insert
	// the key such that the keys in a node are kept sorted!
	// Each node corresponds to a single disk page.
	// The size of a page is 1KB = 1024B.
	// If the node is full, then the full 1024B is
	// being used.

	int currentKey;
	char bufferNew[PageFile::PAGE_SIZE+12];	// Used for storing shifted entries.
	
	// Determine if the node is full. If yes, return an error.
	// To do this, I must check to see if the maximum number
	// of entries are being used.
	if (getKeyCount() == ENTRIES_PER_LEAF)
	{
		fprintf(stderr, "Error: The leaf node is full.\n");
		return RC_NODE_FULL;
	}
	else
	{
		// Start at i=8 since the first 4 bytes stores the # of
		// entries in the node and the second 4 bytes stores the
		// pageid which points to the sibiling node.
		int i = 8;
		while (i < PageFile::PAGE_SIZE)
		{
			memcpy(&currentKey, &buffer[i+8], sizeof(int));
			//cout << "currentKey = " << currentKey << endl;
			// If buffer is not already loaded with entries, currentKey
			// should be 0 due to the constructor.
			if (currentKey == 0)
			{
				// Store the pid from the rid.
				memcpy(&buffer[i], &rid.pid, sizeof(int));

				// Store the sid from the rid.
				memcpy(&buffer[i + sizeof(int)], &rid.sid, sizeof(int));
		
				// Store the key after the record id.
				memcpy(&buffer[i+(2*sizeof(int))], &key, sizeof(int));

				// I also need to increment the # of entries which is
				// stored in the first 4 bytes of the node!!!
				// NOTE: I am assuming that the pageid is located after
				// the 4 byte entry #. So, the first 8 bytes of the
				// node are NOT counted as entries.
				int entry = getKeyCount() + 1;
				memcpy(&buffer[0], &entry, sizeof(int));
				//cout << "entry = " << entry << endl;
				
				//int pid;
				//int sid;
				//int insertkey;
				//memcpy(&pid, &buffer[i], sizeof(int));
				//memcpy(&sid, &buffer[i + sizeof(int)], sizeof(int));
				//memcpy(&insertkey, &buffer[i + (2*sizeof(int))], sizeof(int));
				//cout << "pid = " << pid << endl;
				//cout << "sid = " << sid << endl;
				//cout << "insertkey = " << insertkey << endl;

				return 0;
			}
			else if (currentKey > key)
			{
				// I need to shift all other entries 12 bytes to the right
				// in order to make room for the new entry.
				// First, I will create a copy of the buffer array.
				memcpy(bufferNew, buffer, PageFile::PAGE_SIZE);

				memcpy(&bufferNew[i + 12], &buffer[i], (PageFile::PAGE_SIZE-i));
				
				// After shifting the entries by 12 bytes, re-load the buffer
				// to reflect the change. Now, there should be an empty entry
				// availabe to place the new key and record id.
				memcpy(buffer, bufferNew, PageFile::PAGE_SIZE);
				
				// Store the record id. 
				// NOTE: The record id consists of a
				// page number and a slot number (which are both integers).
				// So, instead of inserting the pointer, I will insert the
				// contents of the pointer.
				
				// Store the pid from the rid.
				memcpy(&buffer[i], &rid.pid, sizeof(int));

				// Store the sid from the rid.
				memcpy(&buffer[i + sizeof(int)], &rid.sid, sizeof(int));
		
				// Store the key after the record id.
				memcpy(&buffer[i+(2*sizeof(int))], &key, sizeof(int));

				// I also need to increment the # of entries which is
				// stored in the first 4 bytes of the node!!!
				// NOTE: I am assuming that the pageid is NOT counted as an entry.
				int entry = getKeyCount() + 1;
				//cout << "entry2 = " << entry << endl;
				memcpy(&buffer[0], &entry, sizeof(int));

				//int pid;
				//int sid;
				//int insertkey;
				//memcpy(&pid, &buffer[i], sizeof(int));
				//memcpy(&sid, &buffer[i + sizeof(int)], sizeof(int));
				//memcpy(&insertkey, &buffer[i + (2*sizeof(int))], sizeof(int));
				//cout << "pid = " << pid << endl;
				//cout << "sid = " << sid << endl;
				//cout << "insertkey = " << insertkey << endl;

				return 0;
			}

			i = i + 12;		// Increment by entries!
		}
	}
	
	//return 0; 
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{ 
	const int RC_SIBLING_NONEMPTY   = -1015;
	const int RC_NODE_NOT_FULL		= -1017;
	int currentKey = 0;

	// Determine if the node is full. If no, return an error.
	// To do this, I must check to see if the maximum number
	// of entries are being used.
	if (getKeyCount() != ENTRIES_PER_LEAF)
	{
		fprintf(stderr, "Error: The leaf node is not full. Do not perform split. \n");
		return RC_NODE_NOT_FULL;
	}

	// If sibling node is not empty, return an error.
	if (sibling.getKeyCount() > 0)
	{
		fprintf(stderr, "Error: The leaf sibling node is not empty.\n");
		return RC_SIBLING_NONEMPTY;
	}

	// For B+ trees, splits occur when there is an overflow in a node
	// after an insert is executed. So, I cannot use the insert function
	// since it would return an error as a result of the overflow. I
	// think I need to create a local buffer array which is 12 bytes
	// larger than the private buffer BTLeafNode variable.
	char bufferExtra[PageFile::PAGE_SIZE+12];
	memcpy(bufferExtra, buffer, PageFile::PAGE_SIZE);
		
	char bufferNewTemp[PageFile::PAGE_SIZE+12];
	memcpy(bufferNewTemp, bufferExtra, PageFile::PAGE_SIZE);

	// NOTE: I need to insert the key such that the keys in a node are kept
	// sorted!

	// Start at i=8 since the first 4 bytes stores the # of
	// entries in the node and the second 4 bytes stores the
	// pageid which points to the sibiling node.
	int i = 8;
	while (i < PageFile::PAGE_SIZE)
	{
		memcpy(&currentKey, &buffer[i+8], sizeof(int));
		//cout << "currentKey = " << currentKey << endl;
		if (currentKey > key)
		{
			// I need to shift all other entries 12 bytes to the right
			// in order to make room for the new entry.
			memcpy(&bufferNewTemp[i+12], &bufferExtra[i], (PageFile::PAGE_SIZE-i));
			
			// After shifting the entries by 12 bytes, re-load the buffer
			// to reflect the change. Now, there should be an empty entry
			// availabe to place the new key and record id.
			memcpy(bufferExtra, bufferNewTemp, PageFile::PAGE_SIZE+12);

			// Store the record id. 
			// NOTE: The record id consists of a
			// page number and a slot number (which are both integers).
			// So, instead of inserting the pointer, I will insert the
			// contents of the pointer.
			
			// Store the pid from the rid.
			memcpy(&bufferExtra[i], &rid.pid, sizeof(int));

			// Store the sid from the rid.
			memcpy(&bufferExtra[i + sizeof(int)], &rid.sid, sizeof(int));
		
			// Store the key after the record id.
			memcpy(&bufferExtra[i+ (2*sizeof(int))], &key, sizeof(int));

			// I also need to increment the # of entries which is
			// stored in the first 4 bytes of the node!!!
			// NOTE: I am assuming that the pageid is NOT counted as an entry.
			int entry = getKeyCount() + 1;
			memcpy(&bufferExtra[0], &entry, sizeof(int));

			//int insertkey;
			//memcpy(&insertkey, &bufferExtra[i + (2*sizeof(int))], sizeof(int));
			//cout << "insertkey = " << insertkey << endl;

			//int firstkey;
			//memcpy(&firstkey, &bufferExtra[16], sizeof(int));
			//cout << "firstkey = " << firstkey << endl;

			break;
		}
		i = i + 12;		// Increment by entry.
	}

	// Now, I must split the node into two. To do this,
	// I need to determine the key count and divide this
	// by two. 
	// NOTE: The number of keys is equivalent to the number
	// of entries in the node.
	int overflowKeyCnt = getKeyCount() + 1;		// Did not update buffer key count yet.
	int newKeyCnt = (int) ceil(overflowKeyCnt/2);
	//cout << "newKeyCnt = " << newKeyCnt << endl;

	// Zero out the buffer in order to re-load it.
	memset(buffer, 0, sizeof(PageFile::PAGE_SIZE));
	memcpy(&buffer[8], &bufferExtra[8], newKeyCnt*3*sizeof(int));

	// Store the new entry count (aka key count) in the buffer.
	memcpy(&buffer[0], &newKeyCnt, sizeof(int));

	// Next, load the rest of the entries in the sibling buffer.
	memcpy(&sibling.buffer[8], &bufferExtra[newKeyCnt*12+8], (overflowKeyCnt-newKeyCnt)*3*sizeof(int));

	// Store the new entry count (aka key count) in the buffer.
	int siblingEntry = overflowKeyCnt-newKeyCnt;
	memcpy(&sibling.buffer[0], &siblingEntry, sizeof(int));
	//cout << "siblingEntry = " << siblingEntry << endl;

	// Next, I have to store the pageid of the sibling's sibling node.
	// The getNextNodePtr() returns the pid of the next sibling node
	int siblingNextPageID = getNextNodePtr();
	memcpy(&sibling.buffer[4], &siblingNextPageID, sizeof(int));

	// Load the first key of the sibling buffer.
	// NOTE: First 4 bytes contains # entries, next 4 bytes contains
	// pageid for sibling node.
	// 4+4+8 = 16 (8 is for pid and sid)
	memcpy(&siblingKey, &sibling.buffer[16], sizeof(int));

	return 0; 
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remember that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{ 
	// NOTE: The first four bytes of a node contains the number of entries!
	int i = 16;		// This gets the first key (Located at 16 bytes from the start).
	int entry = 0;	// NOTE: I will assign 0 as the first entry.
	int key = 0;

	while (i < PageFile::PAGE_SIZE)
	{
		// A record id consists of a page number and slot number,
		// which are both integers. So, I must increment by 8 bytes
		// to get the key value.
		memcpy(&key, &buffer[i], sizeof(int));
		//cout << "key = " << key << endl;
		if (key >= searchKey)
		{
			eid = entry;
			return 0;
		}
		i = i + 12;		// Increment by another 8 bytes to get to the next key.
		entry++;
	}

	// Return an error if did not find the key in the node.
	fprintf(stderr, "Error: Key was not found in leaf node.\n");
	return RC_NO_SUCH_RECORD;

	//return 0;
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{ 
	const int RC_ENTRY_EMPTY   = -1016;

	// Each entry contains 12 bytes (4B for the page number, 4B for
	// the slot number and 4B for the key)

	// I need to read a 4-byte int from a char array... 
	// So, the first 4 locations of the char array are the 4 bytes of the int.
	// I need to convert the 4 bytes into a single integer number. To do this,
	// I will use the memcpy function.
	
	// If no information is stored at the entry number, return an error.
	// NOTE: The page/node is original loaded with 0s!
	// NOTE: First 8 bytes are non-entries.
	// NOTE: The first entry is assigned an eid of 0!
	if (buffer[(eid*12)+16] == 0)
	{
		fprintf(stderr, "Error: Reading empty entry in leaf node.\n");
		return RC_ENTRY_EMPTY;
	}
	else
	{	
		// NOTE: I assumed that eid starts at 0!!!!
		
		// Read the pid.
		memcpy(&rid.pid, &buffer[(eid*12)+8], sizeof(int));

		// Read the sid.
		memcpy(&rid.sid, &buffer[(eid*12+4)+8], sizeof(int));

		// Read the key.
		memcpy(&key, &buffer[(eid*12+8)+8], sizeof(int));
	}

	return 0; 
}

/*
 * Return the pid of the next sibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{ 
	PageId pid;
	memcpy(&pid, &buffer[sizeof(int)], sizeof(int));
	return pid;
	
	//return 0; 
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{ 
	
	if (pid < 0)
	{
		fprintf(stderr, "Error: Invalid pid for next leaf node pointer.\n");
		return RC_INVALID_PID;
	}

	memcpy(&buffer[sizeof(int)], &pid, sizeof(int));
	return 0; 
}

// I added the following constructor in order to create
// an empty non-leaf buffer when a new non-leaf node is generated.
BTNonLeafNode::BTNonLeafNode()
{	
	memset(buffer, 0, PageFile::PAGE_SIZE);
}

// Added helper function to output entire Node contents!!!
RC BTNonLeafNode::printNode()
{ 
	int pid = 0;
	int key = 0;
	int numEntry = 0;
  
	// Entry: 1st part: key, 2nd part: pageid
	// First 8 bytes consists of number of entries and the
	// first pageid.

	memcpy(&numEntry, &buffer[0], sizeof(int));
	cout << "Number of entries = " << numEntry << endl;
	memcpy(&pid, &buffer[4], sizeof(int));
	cout << "PageId = " << pid << endl;

	//cout << "Keycount = " << getKeyCount() << endl;
	int i = 8;
	while (i <= getKeyCount()*8)	// Note had to make <= compared to leaf node.
	{
		memcpy(&key, &buffer[i], sizeof(int));
		memcpy(&pid, &buffer[i + sizeof(int)], sizeof(int));
		cout << key << " ";
		cout << pid << ", ";
		i = i + 8;
	}
	cout << endl;
	//cout << "NextNodePtr = " << getNextNodePtr() << endl;

	return 0; 
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{ 
	RC rc;
  
	// read the page (NOTE: page = node)
	// Before I execute the read, I need to zero out the buffer
	// so that I do not accidentally read in values from a 
	// previous read or write.
	memset(buffer, 0, PageFile::PAGE_SIZE);
	
	// pf is the input PageFile we are reading from.
	// The PageFile buffer is the output of the pf.read method
	// and is writing to the BTNonLeafNode private variable.
	// So, the BTNonLeafNode::read reads from the PageFile buffer
	// and writes to the BTNonLeafNode buffer.
    if ((rc = pf.read(pid, buffer)) < 0)
	{
		fprintf(stderr, "Error: Contents of non-leaf node could not be read. \n");
		return rc;
	}

	return 0; 
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{ 
	RC rc;

	// The PageFile buffer is the input of the pf.write method
	// which is being written to the disk page.
	// So, the BTNonLeafNode::write reads from the BTNonLeafNode buffer
	// and writes to the PageFile.
	if ((rc = pf.write(pid, buffer)) < 0)
	{
		fprintf(stderr, "Error: Contents of non-leaf node could not be written. \n");
		return rc;
	}

	return 0; 
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{ 
	// In the non-leaf node, for every page id there
	// is a key. So, to find the key count, I can
	// simply count the number of page ids.
	int count = 0;

	// the first four bytes of a page contains # entries in the page
	memcpy(&count, buffer, sizeof(int));
	return count;

	//return 0; 
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{ 
	
	// This insert function is similar to BTLeafNode's
	// insert function. I need to insert
	// the key such that the keys in the node are kept sorted!
	// Each node corresponds to a single disk page.
	// The size of a page is 1KB = 1024B.
	// If the node is full, then the full 1024B is
	// being used.

	// NOTE: Each entry in a non-leaf node is 8 bytes.
	// (pageid and key are both 4 bytes)

	int currentKey = 0;
	char bufferNew[PageFile::PAGE_SIZE+8];
	
	// Determine if the node is full. If yes, return an error.
	// To do this, I must check to see if the maximum number
	// of entries are being used.
	if (getKeyCount() == ENTRIES_PER_NONLEAF)
	{
		fprintf(stderr, "Error: The non-leaf node is full.\n");
		return RC_NODE_FULL;
	}
	else
	{
		// Start at i=8 since the first 8 bytes stores the # of
		// entries in the node and the first pageid
		int i = 8;
		while (i < PageFile::PAGE_SIZE)
		{
			memcpy(&currentKey, &buffer[i], sizeof(int));
			// If buffer is not already loaded with entries, currentKey
			// should be 0 due to the constructor.
			if (currentKey == 0)
			{
				// Store the key.
				memcpy(&buffer[i], &key, sizeof(int));
		
				// Store the pid after the key.
				memcpy(&buffer[i+sizeof(int)], &pid, sizeof(int));

				// I also need to increment the # of entries which is
				// stored in the first 4 bytes of the node!!!
				int entry = getKeyCount() + 1;
				memcpy(&buffer[0], &entry, sizeof(int));
				
				return 0;
			}
			else if (currentKey > key)
			{
				// I need to shift all other entries 8 bytes to the right
				// in order to make room for the new entry.
				// First, I will create a copy of the buffer array. Then,
				// I will perform the shift.
				memcpy(bufferNew, buffer, PageFile::PAGE_SIZE);
				memcpy(&bufferNew[i + 8], &buffer[i], (PageFile::PAGE_SIZE-i));
				
				// After shifting the entries by 8 bytes, re-load the buffer
				// to reflect the change. Now, there should be an empty entry
				// availabe to place the new key and page id.
				memcpy(buffer, bufferNew, PageFile::PAGE_SIZE);
				
				// Store the key.
				memcpy(&buffer[i], &key, sizeof(int));
		
				// Store the pid after the key.
				memcpy(&buffer[i+sizeof(int)], &pid, sizeof(int));

				// I also need to increment the # of entries which is
				// stored in the first 4 bytes of the node!!!
				// NOTE: I am assuming that the first four bytes of the
				// node are NOT counted as an entry.
				
				int entry = getKeyCount() + 1;
				memcpy(&buffer[0], &entry, sizeof(int));

				return 0;
			}
			i = i + 8;		// Increment by entries!
		}
	}
	
	//return 0; 

}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{ 
	const int RC_SIBLING_NONEMPTY   = -1015;
	const int RC_NODE_NOT_FULL		= -1017;
	int currentKey = 0;

	// Determine if the node is full. If no, return an error.
	// To do this, I must check to see if the maximum number
	// of entries are being used.
	if (getKeyCount() != ENTRIES_PER_NONLEAF)
	{
		fprintf(stderr, "Error: The non-leaf node is not full. Do not perform split. \n");
		return RC_NODE_NOT_FULL;
	}
	
	// If sibling node is not empty, return an error.
	if (sibling.getKeyCount() > 0)
	{
		fprintf(stderr, "Error: The non-leaf sibling node is not empty.\n");
		return RC_SIBLING_NONEMPTY;
	}
	
	// For B+ trees, splits occur when there is an overflow in a node
	// after an insert is executed.
	// I need to create a local buffer array which is 8 bytes
	// larger than the private buffer BTNonLeafNode variable to 
	// momentarily accomodate the overflow.
	char bufferExtra[PageFile::PAGE_SIZE+8];
	memcpy(bufferExtra, buffer, PageFile::PAGE_SIZE);

	char bufferNewTemp[PageFile::PAGE_SIZE+8];
	memcpy(bufferNewTemp, bufferExtra, PageFile::PAGE_SIZE);

	// NOTE: I need to insert the key such that the keys in a node are kept
	// sorted!

	// Start at i=8 since the first 8 bytes stores the # of
	// entries in the node and the first pageid
	int i = 8;
	while (i < PageFile::PAGE_SIZE)
	{
		memcpy(&currentKey, &buffer[i], sizeof(int));
		if (currentKey > key)
		{
			// I need to shift all other entries 8 bytes to the right
			// in order to make room for the new entry.
			memcpy(&bufferNewTemp[i+8], &bufferExtra[i], (PageFile::PAGE_SIZE-i));
			
			// After shifting the entries by 8 bytes, re-load the buffer
			// to reflect the change. Now, there should be an empty entry
			// availabe to place the new key and record id.
			memcpy(bufferExtra, bufferNewTemp, PageFile::PAGE_SIZE+8);

			// Store the key.
			memcpy(&bufferExtra[i], &key, sizeof(int));

			// Store the pid after the key.
			memcpy(&bufferExtra[i + sizeof(int)], &pid, sizeof(int));

			// I also need to increment the # of entries which is
			// stored in the first 4 bytes of the node!!!
			int entry = getKeyCount() + 1;
			memcpy(&bufferExtra[0], &entry, sizeof(int));

			//int insertkey;
			//memcpy(&insertkey, &bufferExtra[i], sizeof(int));
			//cout << "insertkey = " << insertkey << endl;

			//int firstkey;
			//memcpy(&firstkey, &bufferExtra[8], sizeof(int));
			//cout << "firstkey = " << firstkey << endl;

			//int firstpid;
			//memcpy(&firstpid, &bufferExtra[4], sizeof(int));
			//cout << "firstpid = " << firstpid << endl;

			break;
		}
		i = i + 8;		// Increment by entry.
	}

	// Before I can split the node up into two, I must first
	// find the middle key so that I can move it to the parent.
	// To do this, I need to determine the key count and divide this
	// by two.
	// NOTE: The number of keys is equivalent to the number
	// of entries in the node.
	int overflowKeyCnt = getKeyCount() + 1;		// Did not update buffer key count yet.
	int newKeyCnt = (int) ceil(overflowKeyCnt/2);

	// Now that I have found the number of entries in the node
	// after the insertion, I will find the middle key and load
	// it in midKey. NOTE: This midKey should NOT be stored in
	// either node (current or sibling) since it is moved up 
	// to the parent!
	memcpy(&midKey, &bufferExtra[newKeyCnt], sizeof(int));

	// Now, I must split the node into two such that it and its
	// sibling contains half and half of the contents. 
	// Zero out the buffer in order to re-load it.
	// NOTE: I use (newKeyCnt-1) so that I dont include the midkey
	// when I a redistributing the entries between the two nodes.
	memset(buffer, 0, sizeof(PageFile::PAGE_SIZE));
	memcpy(&buffer[8], &bufferExtra[8], (newKeyCnt-1)*2*sizeof(int));

	// Store the new entry count (aka key count) in the buffer.
	memcpy(&buffer[0], &newKeyCnt, sizeof(int));

	// Next, load the rest of the entries in the sibling buffer.
	// NOTE: I also need to copy over the pagid part of the entry
	// associated with the midKey!!!!!!!!!
	// So, I will first move this pageid, then I will move the remaining
	// entries into the sibling buffer node.
	memcpy(&sibling.buffer[4], &bufferExtra[(newKeyCnt-1)*8+8+4], sizeof(int));
	memcpy(&sibling.buffer[8], &bufferExtra[newKeyCnt*8+8], (overflowKeyCnt-newKeyCnt)*2*sizeof(int));

	// Store the new entry count (aka key count) in the buffer.
	int siblingEntry = overflowKeyCnt-newKeyCnt;
	memcpy(&sibling.buffer[0], &siblingEntry, sizeof(int));

	return 0; 
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{ 
	int currentKey = 0;

	// Start at i=4 since the first 4 bytes stores the # of
	// entries in the node.
	int i = 4;
	while (i < PageFile::PAGE_SIZE)
	{
		memcpy(&currentKey, &buffer[i+4], sizeof(int));			// Retrieve the key
		// NOTE: To output rightmost pageid, I am using the intialization
		// of the rightmost key of 0 to output.
		if ((currentKey == 0) || currentKey >= searchKey)		// Compare key with searchKey
		{
			// If I found the key, then load pid with the pageid that it
			// corresponds with (this is the leftmost pageid).
			memcpy(&pid, &buffer[i], sizeof(int));
			return 0;
		}
		i = i + 8;		// Increment by entries!
	}

	// Return an error if did not find the key in the node.
	fprintf(stderr, "Error: Key was not found in non-leaf node.\n");
	return RC_NO_SUCH_RECORD;

	//return 0; 
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{ 
	
	// Check to see if the parameters are valid.
	if ((pid1 < 0) | (pid2 < 0))
	{
		fprintf(stderr, "Error: Invalid pids given to initialize root.\n");
		return RC_INVALID_PID;
	}

	// NOTE: TA said that keys could be negative values!
	//if (key < 0)
	//{
	//	fprintf(stderr, "Error: Invalid key given to initialize root.\n");
	//	return RC_NO_SUCH_RECORD;
	//}

	// At first, I thought I had to create a page for the root node.
	// However, I realized that the root node can be either a leaf
	// or a non-leaf node! For the purposes of this project, I will
	// treat the root node as a non-leaf node.
    //char bufferNode[PageFile::PAGE_SIZE];

	// NOTE: The root node only has one entry!!!
	int entry = 1;

	// NOTE: pid1 will point to the first non-leaf node and pid2
	// will point to the second non-leaf node.
	memcpy(&buffer[0], &entry, sizeof(int));
	memcpy(&buffer[sizeof(int)], &pid1, sizeof(int));
	memcpy(&buffer[2*sizeof(int)], &key, sizeof(int));
	memcpy(&buffer[3*sizeof(int)], &pid2, sizeof(int));

	return 0; 
}
